package com.wfm.leetcode.editor.cn;

import com.wfm.common.TreeNode;

/**
 * maxGain函数：root的左节点的最大一条路径，maxGain(1) = 1+3 = 4
 *   1
 * 2  3
 */
public class POne24二叉树中的最大路径和{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return max;
    }
    public int maxGain(TreeNode root){
        if(root==null) return 0;
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftMaxGain = Math.max(maxGain(root.left),0);
        int rightMaxGain = Math.max(maxGain(root.right),0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int cur = root.val+leftMaxGain+rightMaxGain;
        max = Math.max(max,cur);

        // 返回节点的最大贡献值，因为是一条路径，只能选一个
        return root.val+Math.max(leftMaxGain,rightMaxGain);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new POne24二叉树中的最大路径和().new Solution();
    }
}